package com.dy.分类.动态规划._152_乘积最大子序列;
/*
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int maxProduct(int[] nums) {
        if(nums.length==1) return nums[0];
        int[] dpmax = new int[nums.length],dpmin = new int[nums.length];
        dpmin[0] = nums[0];
        dpmax[0] = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]<0){
                int tmp = dpmax[i-1];
                dpmax[i-1] = dpmin[i-1];
                dpmin[i-1] = tmp;
            }
            dpmax[i] = Integer.max(dpmax[i-1]*nums[i],nums[i]);
            dpmin[i] = Integer.min(dpmin[i-1]*nums[i],nums[i]);
            max=Integer.max(dpmax[i],max);

        }
        return max;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.maxProduct(new int[]{2,3,-2,4});
    }
}
